\documentclass[submission,revised]{FPSAC2017}

\articlenumber{60}
\addbibresource{60_Aigner.bib}


\graphicspath{{figures/}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{defi}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{rem}[thm]{Remark}
\newtheorem{ex}[thm]{Example}
\newtheorem{com}{Comment}

\newcommand{\ar}{\textnormal{area}}
\newcommand{\Id}{\textnormal{Id}}
\newcommand{\s}{\mathfrak{s}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\st}{(\mathbf{s},\mathbf{t})}



\title[Refined enumerations of ASTs]{Refined enumerations of alternating sign triangles}
\author{Florian Aigner\thanks{\href{mailto:florian.aigner@univie.ac.at}{florian.aigner@univie.ac.at}. Research supported by the Austrian Science Fund (FWF), START grant Y463.}}
\address{Fakult\"at f\"ur Mathematik, Universit\"at Wien, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria}

\received{November 14, 2016}

\revised{}

\abstract{
We generalise alternating sign triangles, which were recently introduced by Ayyer, Behrend and Fischer and shown to be equinumerous with ASMs, to AS-trapezoids and introduce a refinement by Catalan objects. We show that the number of AS-trapezoids associated with a fixed Catalan object is a polynomial in the length of the shorter base of the trapezoid.
As a special case we obtain an analogue of a polynomiality theorem for fully packed loops with nested arches.
}

\keywords{Alternating sign triangles, AS-trapezoids, polynomial enumeration formula, centred Catalan sets, Motzkin paths}







\begin{document}

\maketitle

\section*{Introduction}

In the 1980s Mills, Robbins and Rumsey \cite{ASMs} introduced \emph{alternating sign matrices} (ASMs) and thereby initiated a new branch in combinatorics. Over time more combinatorial objects were introduced which are equinumerous to ASMs, e.\,g. \emph{fully packed loops} (FPLs). FPLs led in a natural way to a refined enumeration by means of Catalan objects. This refinement gave rise to a variety of important results, one of them is the Razumov-Stroganov-Cantini-Sportiello Theorem \cite{Razumov-Stroganov-Proof,Razumov-Stroganov-Conj}. A new object in the `ASM-family' are \emph{alternating sign triangles} (ASTs) which were introduced by Ayyer, Behrend and Fischer. They could show in \cite{AST} that ASTs and ASMs are equinumerous. While there exists an easy bijection between ASMs and FPLs there is no bijection known between ASMs and ASTs.



In this extended abstract we present a refinement of ASTs via Motzkin paths (due to Ayyer) and by Catalan objects (\emph{centred Catalan sets}). One can see already for smaller examples that this Catalan refinement is of different nature than the one for FPLs.
Our first main result is a proof of a conjecture of Ayyer. It states that an AST associated with a fixed Motzkin path $M$ or a centred Catalan set $S$ can be split into independent parts if and only if $M$ or $S$ respectively is reducible. This implies that the number of ASTs associated with a certain Motzkin path $M$ or a centred Catalan set $S$ respectively is given by a product of \emph{weight functions}, each depending on a irreducible component of $M$ or $S$ respectively and its position in $M$ or $S$ respectively.

The aforementioned independent parts are \emph{AS-trapezoids}, which generalise ASTs. By extending the centred Catalan set or Motzkin path assignment from ASTs to AS-trapezoids, we see that the weight functions count refined AS-trapezoids.
Our second main result states that the number of AS-trapezoids associated to a fixed centred Catalan set or Motzkin path respectively is a polynomial in the length of the shorter base of the trapezoid. Computations indicate that the polynomials have various rational roots. We present first results on the structure of these roots and state two conjectures concerning them.


Finally we show that in a special case of our second main result is an analogue to a polynomiality theorem for FPLs conjectured by Zuber in \cite{Zuber} and later proven in \cite{Aigner, on_the_number_of_FPL} by Caselli, Krattenthaler, Lass and Nadeau, and Aigner.



\section{Preliminaries}
 We first introduce alternating sign triangles which were recently defined in \cite{AST}. Then we define centred Catalan sets, which are in bijection to Dyck paths, and Motzkin paths and how to associate these objects to an AST.
  
 
 \begin{defi}
An \emph{alternating sign triangle (AST)} of order $n$ is a configuration of $n$ centred rows where the $i$-th row, counted from the bottom, has $2i-1$ elements. The entries are $-1,0$ or $1$ such that in all rows and columns the non-zero elements are alternating, all row-sums are $1$ and in every column the first non-zero entry from top is positive.
 \end{defi}
 
 We label the columns of an AST $A$ of order $n$ form left to right with $-(n-1), \ldots, n-1$ and the rows from bottom to top with $1, \ldots, n$.
 
 
\begin{ex}
\label{ex: AST}
  The following is an example of an AST of order $6$
 \[
\begin{array}{c	c c c c c c c c c c}
0 & 0 & 0& 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
  & 0 & 0 & 1 &0 & 0 & 0 & 0 & 0 &0\\
  &   &   1 & -1 & 0& 0  & 0 & 0 &1\\
  &   &     &  0  & 0 & 1 & 0 & 0\\
  &   &     &     & 1 & -1 & 1\\
  & & & & &1
\end{array}
\]
\end{ex}

 
 
 
 \begin{thm}[{\cite{AST}}]
 The number of ASTs of order $n$ is given by
 \[
 \prod_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!},
 \]
 i.\,e. order $n$ ASTs and $n \times n$ ASMs are equinumerous.
 \end{thm} 
 
 


\begin{defi}
A \emph{centred Catalan set} $S$ of size $n$ is an $n$-subset of $\{-(n-1),-(n-2),\ldots, n-1\}$ such that $|S \cap \{-i,-i+1, \ldots, i\}| \geq i+1$ for all $0 \leq i \leq n-1$.
\end{defi}




The centred Catalan sets of size $n$ are in bijection with Dyck paths of length $2n$. For a given centred Catalan set $S$, we construct a Dyck path $D(S)$ in the following way. We read the integers $-(n-1), \ldots, n-1,n$ in the order $0,-1,1,-2,2,\ldots,-(n-1),n-1,n$ and draw a north-east step if the number is in $S$ and a south-east step otherwise.
There are in total $2^{n-1}$ different bijections of the above kind between centred Catalan sets of size $n$ and Dyck paths of length $2n$. For every $1 \leq i \leq n-1$ we can switch the order of reading $-i,i$ in the above algorithm and obtain a new bijection.


\begin{figure}
$\{-3,-1,0,1,3,4\} \quad \Leftrightarrow \quad$
 \centering
 \includegraphics[scale=1.5]{Dyck}
 \caption{\label{fig: Dyck} A centred Catalan set of size $6$ and its corresponding Dyck path.}
\end{figure}

\begin{prop}
\label{prop: AST to cCS}
 Let $S(A)$ be the set of labels of columns with positive column-sum. Then $S(A)$ is a centred Catalan set of size $n$ and for all centred Catalan sets $S$ of size $n$ there exists an AST $A$ of order $n$ with $S(A)=S$.
\end{prop}
\begin{proof}
The set $S(A)$ is an $n$-subset of $\{-(n-1),\ldots,n-1\}$. Define $S_i(A)$ as the set of columns $j$ such that $|j|<i$ and the partial column-sum of elements below the $(i+1)$-th row is positive. We have the following relations between $S_i(A)$ and $S(A)$
\begin{align*}
S(A)&= \bigcup_{1 \leq i \leq n}S_i(A),\\
S_{i+1}(A) &\subseteq S \cap \{-i,-i+1, \ldots,i\}.
\end{align*}
Since the partial column-sums can only have the values $1,0,-1$ and the sum of all these partial column-sums is $i$ we obtain $|S_i(A)| \geq i$, which implies the first claim. Now let $S$ be given. By definition we can choose a sequence $(s_i)_{1 \leq i \leq n}$ such that $S=\{s_i: 1 \leq i\leq n\}$ and $|s_i| < i$. Hence there exists an AST such that the entry in column  $s_i$ of the $i$-th row is $1$ for all $1 \leq i \leq n$ and the other entries are $0$.
\end{proof}


A \emph{Motzkin path} of length $n$ is a path on the half-plane $y \geq 0$ starting at $(0,0)$ and ending at $(n,0)$ with step-set $\{(1,1),(1,0),(1,-1)\}$. We encode a Motzkin path $M$ of length $n$ by a sequence $M=(m_1,\ldots,m_n)$ with entries $m_i \in \{1,0,-1\}$ for $1 \leq i \leq n$ where an entry $m_i$ encodes the step $(1,m_i)$.
We define $M(D)$ as the Motzkin path obtained by averaging the steps in the Dyck path $D$: the $i$-th step of $M(D)$ is the average of the $(2i)$-th and $(2i+1)$-th step of $D$. By averaging we mean that two north-east steps result in a north-east step, a north-east step and a south-east step in an east step and two south-east steps in a south-east step. This map is a surjection from Dyck paths of length $2n$ to Motzkin paths of length $n-1$. 
For a centred Catalan set $S$ of size $n$ the Motzkin path $M(S):=M(D(S))=(m_1(S), \ldots,m_{n-1}(S))$ is given by
\[
m_i(S):=
\begin{cases}
1 \quad & |\{-i,i\} \cap S|=2,\\
0 & |\{-i,i\} \cap S|=1,\\
-1 & |\{-i,i\} \cap S|=0.
\end{cases}
\]

The following refinement of ASTs by Motzkin paths is due to Ayyer.

\begin{cor}
 \label{cor: Motzkin paths and ASTs}
  The map $M(A):=M(S(A))$ is a surjection from ASTs of order $n$ to Motzkin paths of length $n-1$.
\end{cor}



\begin{figure}
 \centering
 \includegraphics[scale=1.1]{Dyck_to_Motzkin}
 \caption{\label{fig: Dyck} A Dyck path and its corresponding Motzkin path.}
\end{figure}




















\section{The structure of ASTs}

For two Motzkin paths $M_1,M_2$ we denote by  $M_1\circ M_2$ their concatenation. Ayyer conjectured that the number $w(M)$ of ASTs associated to the Motzkin path $M=M_1\circ M_2$ is a product of two weight functions each depending on $M_1$ and $M_2$ respectively and its position in $M$. We found out that this computational fact is based on a structural reason, namely that we can split an AST associated to $M_1\circ M_2$ into two independent parts, one associated to $M_1$ the other to $M_2$. The next lemma plays a key role.



\begin{lem}
\label{lem: structure of ones}
Let $S$ be a centred Catalan set of size $n$ and $A$ an AST with $S(A)=S$ and write $M(S)=(m_1, \ldots m_{n-1})$.
The number of $1$ entries in the $(r+1)-th$ row is at most $1+\sum_{i=1}^r m_i$. Further there exists an AST such that equality holds.
\end{lem}

\begin{proof}
An \emph{allowed position} for a $1$ in the $i$-th row of $A$ is a position such that the next non-zero entry below is negative or all entries below are $0$ and the label of the column is in $S$.
Denote by $a_i$ the number of allowed positions for a $1$ in the $i$-th row. Since every $1$ (respectively $-1$) in the $i$-th row cancels out (respectively adds) an allowed position for a $1$ in the $(i+1)$-th row and there is one more $1$ than $-1$ in every row, the number of allowed positions in the central $2i-1$ columns of the $(i+1)$-th row is $a_i-1$. There are two new columns in row $i+1$ of which $m_i+1$ have a label in $S$. Hence we obtain $a_{i+1}=a_i+m_i$ and therefore
\[
 a_{i+1}=a_1+\sum_{j=1}^{i} m_i=1+\sum_{j=1}^{i} m_i.
\]


We construct an AST $A$ with $S(A)=S$ and a maximal number of $1$'s in a recursive manner. Place in the $i$-th row a $1$ in all allowed positions and put a $-1$ between the $1$ entries. Since the allowed positions are either the most left or right positions of a row or above a $-1$ from the row before, two allowed positions are by induction not direct neighbours. Therefore it is always possible to place a new row by the above algorithm. By the above formula there is only one allowed position in the top row. If there exists a column in $A$ with a $-1$ as first non-zero entry form top there would be a second allowed position in the top row. Hence the resulting array is an AST.
\end{proof}





We say that a Motzkin path $M$ is \emph{irreducible} if and only if there exist no Motzkin paths $M_1,M_2$ such that $M$ can be written as concatenation $M_1\circ M_2$ of the two paths.
Let $l$ be an integer and define the dilation operator $\s_l: \Z \rightarrow \Z$ as
\[
\s_l(x)=
\begin{cases}
x+l \quad &x>0,\\
0 & x=0,\\
x-l & x<0.
\end{cases}
\]
By abuse of notation we write $\s_l: 2^\Z \rightarrow 2^\Z, \;\s_l(A)=\{\s_l(x)|x\in A\}$. 
We call a centred Catalan set $S$ of size $n$ \emph{irreducible} if there exist no centred Catalan sets $S_1,S_2$ of sizes $n_1$ or $n-n_1+1$ respectively such that $S=S_1 \cup \s_{n_1-1}(S_2)$.
We can split every centred Catalan set $S$ uniquely into irreducible centred Catalan sets $S_1, \ldots, S_l$ of size $n_1,\ldots, n_l$ such that
\[
 S=S_1 \cup \s_{n_1-1}(S_2) \cup \cdots \cup \s_{j_l}(S_l),
\]
where $j_l=\sum_{i=1}^{l-1}(n_i-1)$.
We denote this splitting by $S=(S_1, \ldots,S_l)$. The Dyck path $D((S_1, \ldots,S_l))$ is obtained by deleting the last step of $D(S_1), \ldots, D(S_{l-1})$, deleting the first step of $D(2),\ldots D(S_l)$ and concatenating all paths.
The Motzkin path $M((S_1, \ldots,S_l))$ is given as the concatenation of the Motzkin paths of its irreducible components
$M(S_1)\circ M(S_2) \circ \ldots \circ M(S_l)$.
Further every irreducible component of $M(S)$ corresponds to an irreducible component of $S$.
For an example see \cref{fig: Splittings}.\\






\begin{figure}
 \centering
 \includegraphics[width=.9\textwidth]{Splittings}
  \caption{\label{fig: Splittings} The Dyck and Motzkin paths of the centred Catalan set $S=\{-3,-1,0,1,3,4\}$ and its irreducible components $S_1=\{-1,0,1\}$ and $S_2=\{-1,0,1,2\}$.
  }
\end{figure}





We define the \emph{weight} $w(S)$ (respectively $w(M)$) of a centred Catalan set $S$ (respectively Motzkin path $M$) as the number of ASTs $A$ with $S(A)=A$ (respectively $M(A)=M$).




\begin{defi}
An $(n,l)$-\emph{AS-trapezoid} is an array of $n$ centred rows where the $i$-th row from bottom has $2(l+i)-1$ entries, filled with $-1,0$ or $1$ such that all row-sums are $1$, the column-sums are $0$ for the central $2l-1$ columns, the non-zero entries in all rows and columns are alternating and in every row the first non-zero entry from top is positive.
\end{defi}

ASTs of order $n+1$ and $(n,1)$-AS-trapezoids are in bijection by deleting the bottom $1$ of an AST or adding a $1$ in the bottom of an $(n,1)$-AS-trapezoid. We label the rows of an $(n,l)$-AS-trapezoid from bottom to top with $1,\ldots, n$ and the columns from left to right by $-(n+l-1), \ldots, (n+l-1)$. We define the set $S(A)$ as the centred Catalan set $S$ such that $\s_{l-1}(S)\setminus\{0\}$ is the set of columns of $A$ with positive column-sum. Analogously to \cref{prop: AST to cCS} the set $S(A)$ is indeed a centred Catalan set. The following is an example of a $(3,3)$-AS-trapezoid $A$ with $S(A)=\{-1,0,1,2\}$
\[
\begin{array}{c	c c c c c c c c c c}
0 & 0 & 0& 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
  & 0 & 0 & 1 &0 & 0 & 0 & 0 & 0 &0\\
  &   &   1 & -1 & 0& 0  & 0 & 0 &1\\
\end{array}
\]

For a centred Catalan set $S$ of size $n+1$ we define $w_l(S)$ as the number of $(n,l)$-trapezoids $A$ with $S(A)=S$.




\begin{thm}
\label{thm: multiplicity of Catalan weight}
For centred Catalan sets $S_1,S_2$ of size $l$ or $n+1$ respectively holds
\begin{equation}
\label{eq: multiplicity of weights}
w(S_1 \cup \s_{l-1}(S_2))=w(S_1)w_{l}(S_2),
\end{equation}
i.\,e. the weight function is ``multiplicative''.
\end{thm}

\begin{proof}
Let $A_1$ be an AST of order $l$ and $A_2$ an $(n,l)$-AS-trapezoid such that $S(A_i)=S_i$ for $i=1,2$. By putting $A_2$ on top of $A_1$ we obtain an AST $A$ of order $n+l$ with $S(A)=(S_1,S_2)$.
On the other hand let $A$ be an AST with $S(A)=S=S_1 \cup \s_{l-1}(S_2)$. We split $A$ into a bottom part $A_1$ consisting of the first $l$ rows from bottom and a top part $A_2$ consisting of the remaining rows.
By \cref{lem: structure of ones} there is only one allowed position for a $1$ in the top row of $A_1$.
If $A_1$ had a column whose first non-zero entry from top is negative, there would be a second allowed position for a $1$ in the top row of $A_1$. Hence $A_1$ is an AST of order $l$ with $S(A_1)=S_1$. A column of $A$ with label $-l < \lambda < l$ has column-sum $1$ if and only if $\lambda \in S_1=S(A_1)$. Hence the column-sums of the central $2l-1$ columns of $A_2$ are zero, which implies that $A_2$ is an $(n,l)$-AS-trapezoid and $A_1$ and $A_2$ are independent. The definitions of the weight functions imply \eqref{eq: multiplicity of weights}.
\end{proof}



The following Corollary was a former conjecture by Ayyer.


\begin{cor}
Define for a Motzkin path $M$ the weight $w_l(M)$ as the number of $(n,l)$-AS-trapezoids $A$ with $M(S(A))=M$. Then \cref{thm: multiplicity of Catalan weight} holds analogously for Motzkin paths instead of centred Catalan sets.
\end{cor}

























\section{The refined enumeration of AS-trapezoids}

The aim of this section is to prove that the weight function $w_l(S)$ is a polynomial in $l$. First we need the following definition which is due to Fischer \cite{Ilse}.



\begin{defi}
 Let $1 \leq u<v \leq n$, $\mathbf{s}=(s_1,\ldots,s_u)$ be a weakly decreasing sequence of non-negative integers, $\mathbf{t}=(t_{v},\ldots,t_n)$ a weakly increasing sequence of non-negative integers and $\mathbf{k}=(k_1 ,\ldots,k_n)$ an increasing sequence of integers.
 An $\st$-tree with bottom entries $\mathbf{k}$ is a triangular array of integers with the following properties:
 \begin{itemize}
  \item The  entries are weakly increasing in north-east and south-east direction and strictly increasing in east direction.
  \item For $1 \leq i \leq u$ the bottom $s_i$ elements in the $i$-th north-east diagonal are deleted and the bottom entry of this north-east diagonal is $k_i$. This entry does not have to be less than its right neighbour.
  \item For $v \leq i \leq n$ the bottom $t_i$ elements in the $i$-th south-east diagonal are deleted. The bottom entry of this south-east diagonal is $k_i$. This entry does not have to be greater than its left neighbour.
  \item The entries in the bottom row are $k_{u+1},\ldots, k_{v-1}$.
 \end{itemize} 
\begin{figure}
 \centering
 \includegraphics{s,t_tree}
  \caption{\label{fig: s,t_tree} Schematic diagram of an $\st$-tree.
  }
\end{figure}
\end{defi}


Let $S$ be an irreducible centred Catalan set of size $n+1 \geq 3$. We write $S=\{-s_1-1, \ldots, -s_u-1,-1,0,1,t_{u+3}+1, \ldots,t_{n}+1\}$ where $(s_i)_{1 \leq i \leq u}$ or $(t_i)_{u+3\leq i \leq n}$ is a decreasing sequence or an increasing sequence respectively of positive integers. Set $\mathbf{s}=(s_1,\ldots, s_u)$, $\mathbf{t}=(t_{u+3}, \ldots,t_n)$ and $\mathbf{k}=(-l-s_1,\ldots,-l-s_u,-l,l,l+t_{u+3},\ldots,l+t_n)$.
The following algorithm is a bijection between $(n,l)$-AS-trapezoids $A$ with $S(A)=S$ and $\st$-trees with bottom entries $\mathbf{k}$.
First we construct a triangular array $T_A$. We fill the $i$-th row from bottom of $T_A$ by the column labels of $A$ for which the first non-zero entry above the $i-1$-th row is positive. Thereby we write the numbers in an increasing order from left to right. The bottom row of $T_A$ is $\mathbf{k}$. Since in every row of the trapezoid there is one more $1$ than $-1$ the number of entries in a row of $T_A$ is one less than the number of entries in the row below. Further it is easy to see that the entries of $T_A$ are weakly increasing in north-east and south-east direction.
Since the column-sum of the $(-l-s_i)$-th column of $A$ is $1$, the first $s_i+1$ entries of the $i$-th north-east diagonal of $T_A$ for $1 \leq i \leq u$ will be $(-l-s_i)$. Hence we can delete without loss of information $s_i$ of them. Analogously the first $t_i+1$ entries of the $i$-th north-east diagonal of $T_A$ will be $l+t_i$ for $u+3 \leq i \leq n$ and we can delete $t_i$ of them. The resulting array $T_A$ is an $\st$-tree with bottom entries $\mathbf{k}$.
On the other hand it is not difficult to see that every such $\st$-tree is of the form $T_A$.

\begin{prop}
\label{prop: bij s,t-trees}
 Let $S$ be an irreducible centred Catalan set of size $n+1 \geq3$. The map $A \mapsto T_A$ from $(n,l)$-AS-trapezoids to $(\mathbf{s},\mathbf{t})$-trees with bottom entries $\mathbf{k}$ as described above is a bijection.
\end{prop}


\begin{ex}
Let $S=\{-1,0,1,2\}$ and $-l<a<l$. The $(3,l)$-AS-trapezoids as on the left side of \eqref{eq: ASTt to st-trees}, where the $-1$ is in column $a$, correspond by the above algorithm to the $\st$-trees with bottom entries $\mathbf{k}$ on the right side of \eqref{eq: ASTt to st-trees}, where $\mathbf{s},\mathbf{t},\mathbf{k}$ are defined as before.
\begin{align}
\label{eq: ASTt to st-trees}
\begin{array}{ccccccccccccc}
0 & 0 & 0 & \cdots & 0 & 0 &  0 & \cdots & 0 & 0 & 1 & 0\\
  & 0 & 0 & \cdots & 0 & 1 &  0 & \cdots & 0 & 0 & 0\\
  &   & 1 & \cdots & 0 &-1 &  0 & \cdots & 0 & 1
\end{array} \qquad \leftrightarrow \qquad
\begin{array}{cccc}
& & l+1\\
& a & & l+1\\
-l & & l
\end{array} .
\end{align}
\end{ex}





Let $f$ be a function in $x$. Denote by $\overline{\Delta}_{\textit{ }x}(f):= f(x+1)-f(x)$ the forward difference of $f$ and by $\underline{\Delta}_{\textit{ }x}:= f(x)-f(x-1)$ the backward difference of $f$.






\begin{thm}[{\cite{s_t_trees}}]
\label{thm: s_t_trees}
 Set 
 \begin{equation}
  \label{eq: def alpha}
  \alpha(n;k_1,\ldots,k_n):= \prod_{1 \leq p < q \leq n}(\Id+ 
  \overline{\Delta}_{\textit{ }k_p}\overline{\Delta}_{\textit{ }k_q}+\overline{\Delta}_{\textit{ }k_q})
  \prod_{1 \leq p < q \leq n} \frac{k_q-k_p}{q-p}.
 \end{equation}
 The number of $\st$-trees with bottom entries $\mathbf{k}=(k_1 ,\ldots,k_n)$ is given by
 \begin{equation}
  \label{eqn: s_t_trees}
  (-\overline{\Delta}_{\textit{ }k_1}^{\textit{ }s_1}) \cdots
  (-\overline{\Delta}_{\textit{ }k_u}^{\textit{ }s_u})
  \underline{\Delta}_{\textit{ }k_{v}}^{\textit{ }t_{v}} \cdots
  \underline{\Delta}_{\textit{ }k_{n}}^{\textit{ }t_{n}}
  \alpha(n;k_1,\ldots,k_n).
 \end{equation}
\end{thm}







With the above theorem at hand it is not difficult to prove the following theorem.





\begin{thm}
 \label{thm: Catalan weight is polynomial}
 Let $S$ be a centred Catalan set of size $n+1$. The weight $w_l(S)$ is a polynomial in $l$ of degree $\ar(M(S))$, where $\ar(M(S))$ denotes the area enclosed by $M(S)$ and the $x$-axis. 
\end{thm}

\begin{proof}
\cref{thm: multiplicity of Catalan weight} implies $w_l((S_1,S_2))=w_{l}(S_1)w_{l+|S_1|-1}(S_2)$. Hence it suffices to assume $S$ to be irreducible. 
 Let $\mathbf{s},\mathbf{t},\mathbf{k}$ be as above. \cref{thm: s_t_trees} implies that the number of $\st$-trees with bottom row $\mathbf{k}$ is a polynomial in $l$. Denote by $d(S)$ the degree of $w_l(S)$.
 We show by induction on $\ar(M(S))$ that $d(S) \leq \ar(M(S))$. The degree $d(S)$ is at most the degree of the polynomial $\alpha(n;k_1,\cdots,k_n)$ minus the number of $\overline{\Delta}, \underline{\Delta}$ operators appearing in \eqref{eqn: s_t_trees}
 \begin{equation}
  \label{eqn: degree inequality}
  d(S) \leq \binom{n}{2} - \sum_{i=1}^u s_i -\sum_{i=u+3}^n t_i =
  \binom{n}{2}- \sum_{i \in S\setminus\{0\}}(|i|-1).
  \end{equation}
 It suffices to show $\binom{n}{2}=\sum_{i \in S\setminus\{0\}}(|i|-1) + \ar(M(S))$. If $\ar(M(S))=0$, exactly one of $i$ and $-i$ is in $S$ for all $1 \leq i \leq n$, hence $\sum_{i \in S\setminus\{0\}}(|i|-1)= \sum_{i=1}^n (i-1)=\binom{n}{2}$.
 If $\ar(M(S))>0$ denote by $i_0$ the largest integer with $1 \leq i_0 \leq n-1$ and $\{-i_0,i_0 \} \subseteq S$. It follows that the set 
 \[
 S^\prime:=\begin{cases}
 (S\setminus\{i_0\}) \cup \{ i_0+1\} & (i_0+1) \notin S,\\
 (S\setminus\{i_0\}) \cup \{ -(i_0+1)\} & -(i_0+1) \notin S,\\
 \end{cases}
 \]
  is a centred Catalan set. The paths $M(S)$ and $M(S^\prime)$ differ only in the $i_0$-th and $(i_0+1)$-th step as shown in \cref{fig: change of S}. This implies that $\ar(M(S^\prime))=\ar(M(S))-1$. On the other hand the sum over all $i \in S\setminus\{0\}$ in \eqref{eqn: degree inequality} is one less than the sum over all $i \in S^\prime\setminus \{0\}$ which proves the claim.
 \begin{figure}
 \centering
 \includegraphics{proof_poly}
 \caption{\label{fig: change of S} The two possibilities of changes between $M(S)$ and $M(S^\prime)$ at the positions $i_0,i_0+1,i_0+2$.}
\end{figure}

We conclude the proof by showing the existence of a subset of $\st$-trees with bottom entries $\mathbf{k}$  which grows polynomial in $l$ of degree $\ar(M(S))$. By a similar proof as for the degree above we can show that there are $\ar(M(S))$ entries in an $\st$-tree which are not fixed by definition. Let us denote these entries by $x_1, \ldots, x_{\ar(M(S))}$. For  $l \geq \left\lceil \frac{\ar(M(S))-1}{2} \right\rceil$ there exists an  $\st$-tree $T$ such that the entries $x_1, \ldots, x_{\ar(M(S))}$ are pairwise different and lie between $-l$ and $l$. We relabel these entries such that $-l \leq x_1 < \ldots < x_{\ar(M(S))} \leq l$ holds. The number of $\st$-trees with bottom entries $\mathbf{k}$ and $-l \leq x_1 < \ldots < x_{\ar(M(S))} \leq l$ is given by
\[
 |\{(x_1, \ldots, x_{\ar(M(S))}): -l \leq x_1 < \ldots < x_{\ar(M(S))} \leq l\}| = \binom{2l+1}{\ar(M(S))}. \qedhere
\]
\end{proof}



\begin{cor}
\cref{thm: Catalan weight is polynomial} holds analogously for $w_l(M)$ where $M$ is a Motzkin path.
\end{cor}



\begin{rem}
Let $\pi$ denote the bijection between Dyck paths of length $2n$ and noncrossing matchings of size $n$. Let $S_1,S_2$ be two centred Catalan sets of size $n_1$ or $n_2$ respectively and $m$ a positive integer.
We define $S(m)=S_1 \cup \{n_1, n_1+1,\ldots,n_1+m-1\} \cup \s_{n_1+m-1}(S_2)$.
The noncrossing matching $\pi(D(S(m)))$ consists of the two matchings $\pi(D(S_1))$ and $\pi(D(S_2))$, which are separated by $m$ `small arches'.
By \cref{thm: multiplicity of Catalan weight} and \cref{thm: Catalan weight is polynomial} the weight $w(S(m))=w(S_1)w_{n_1+m}(S_2)$ is a polynomial in $m$. 
An analogous theorem \cite[Thm $1.1$]{Aigner} exists for fully packed loops (FPLs) which are equinumerous to ASTs. It states that the number of FPLs whose associated noncrossing matching is given by two noncrossing matchings $\pi_1$ and $\pi_2$, separated by $m$ `nested arches', is a polynomial in $m$. This is remarkable since the refinements of ASTs or FPLs respectively by Catalan objects are of different nature and the polynomiality theorems differ (beside the statements for the degree and leading coefficient) only in the dual notions `nested arches' and `small arches'.
\end{rem}

 
 \noindent The following table lists the weight functions of irreducible Motzkin paths up to size $5$.
    
       
	\begin{tabular}{cl}
           $M$ & $w_l(M)$\\
           \hline
           \includegraphics[scale=0.5]{m1} & $2$\vspace{2 pt}\\
           \includegraphics[scale=0.5]{m2} & $(2l+1)$\vspace{2 pt}\\
           \includegraphics[scale=0.5]{m3} & $2(2l+1)(l+2)$\\
           \includegraphics[scale=0.5]{m4} & $\frac{1}{3}(2l+1)(l+1)(l+3)(2l+7)$\vspace{2 pt}\\
           \includegraphics[scale=0.5]{m5} & $4(2l+1)(l+2)(l+3)$\\
           \includegraphics[scale=0.5]{m6} & $\frac{1}{9}(2l+1)(l+1)(2l+7)(2l^3+23l^2+84l+90)$\\
           \includegraphics[scale=0.5]{m7} & $\frac{2}{3}(2l+1)(l+1)(l+3)(l+4)(2l+7)$\\
           \includegraphics[scale=0.5]{m8} & $\frac{2}{3}(2l+1)(2l^4+25l^3+113l^2+216l+147)$\vspace{2 pt}\\
           \includegraphics[scale=0.5]{m9} & $8(2l+1)(l+2)(l+3)(l+4)$\vspace{2 pt}
       \end{tabular}
 
 
 
 As one can see in the above table, the polynomials $w_l(M)$ (and analogously $w_l(S)$) are rich in rational roots. The following two propositions give first explanations for these.


\begin{prop}
\label{prop: adding a height one piece}
Let $M$ be a Motzkin path of length $n$ ending with an south-east step and denote by $M^\prime$ the Motzkin path of length $n+1$ obtained by putting an east step in front of the last step of $M$, i.\,e., if $M=(1,-1)$ then $M^\prime=(1,0,-1)$. The weight $w_l(M^\prime)$ is given by
\[
w_l(M^\prime)=2(l+n)w_l(M).
\]
\end{prop}

\begin{proof}
Let $A^\prime$ be an $(n+1,l)$-AS-trapezoid with $M(A^\prime)=M^\prime$. If $A^\prime$ doesn't have a $-1$ in the second last row from top, the last two rows have up to horizontal and vertical reflection of the inner $2(n+l)-1$ columns the form
\[
\begin{array}{c	c c c c c}
0 &1 &0\, \cdots\, 0 &0 &0\, \cdots \,0 &0\\
&0 &0 \,\cdots\, 0 &1 &0 \,\cdots \,0
\end{array}.
\]
By reflecting the top two rows in such a way such that one obtains the above form and deleting the top row we obtain an $(n,l)$-AS-trapezoid $A$ with $M(A)=M$.
Now assume $A^\prime$ has a $-1$ entry in its second last row from top. Then the two top rows have up to horizontal reflection the form 
\[
\begin{array}{c	c c c c c c c}
0 &0 &0\, \cdots\, 0 &1 &0\, \cdots \,0 &0 &0\, \cdots \,0 &0\\
&1 &0 \,\cdots\, 0 &-1 &0 \,\cdots \,0 &1 &0 \,\cdots \,0
\end{array}.
\]
If we delete the top row and delete in the second row from top the left $1$ and the $-1$ we obtain again an $(n,l)$-AS-trapezoid $A$ with $M(A)=M$.
On the other hand starting from an $(n,l)$-AS-trapezoid $A$ we can construct $4$ or $2(n+l-2)$ AS-trapezoids $A^\prime$ with no $-1$ or one $-1$ respectively in the second row from top and $M(A^\prime)=M^\prime$, which proves the claim.
\end{proof}




\begin{prop}
 \label{prop: divisibility by 2j+1}
 Let $S$ be an irreducible centred Catalan set of size $n+1 \geq 3$ then $w_l(S)$ is divisible by $(2l+1)$. 
\end{prop}

\begin{proof}
Let $\mathbf{s}, \mathbf{t}, \mathbf{k}$ be as before. Denote by $\mathbf{s}^\prime, \mathbf{t}^\prime$ the sequences $\mathbf{s}, \mathbf{t}$ but with the entry $1$ removed and set $\mathbf{k}^\prime$ equals the sequence $\{k_1, \ldots,k_n\}$ but with the variable $x$ instead of $-l,l$.
The $(\mathbf{s}^\prime,\mathbf{t}^\prime)$-trees with $\mathbf{k}^\prime$ as bottom entries and $-l \leq x \leq l$ correspond to the $\st$-trees where the bottom row is deleted.
Let $f(l,x)$ be the function that counts the number of $(\mathbf{s}^\prime,\mathbf{t}^\prime)$-trees with bottom entries $\mathbf{k}^\prime$. By \cref{thm: s_t_trees} $f(l,x)$ is a polynomial in $l$ and $x$. The weight $w_l(S)$ is given by
\[
 w_l(S)=\sum_{x=-l}^l f(l,x) = \left(\sum_{x=0}^{L}f(l,x-l)\right)_{|L=2l}.
\]
Let $p(x)$ be a polynomial in $x$ and define
\begin{equation}
 P(x)=\begin{cases}
       \sum_{i=0}^x p(i) \quad &x \geq 0,\\
       0 &x=-1,\\
       -\sum_{i=x+1}^{-1} p(i) & x<0.       
      \end{cases}
\end{equation}
It is well known that $P(x)$ is again a polynomial. This implies in our case
\[
 w_{-\frac{1}{2}}(S)=\sum_{x=0}^{-1}f(-\frac{1}{2},x+\frac{1}{2})=0.
 \qedhere
\]
\end{proof}




Computations indicate that the above proposition holds in a more general form.





\begin{conj}
Let $S$ be an irreducible Catalan set. For every positive integer $i$ there exists a polynomial $f_i(l)$ which decomposes into linear factors  over $\mathbb{Q}$ such that
\[
\{-i,\ldots, i\} \subseteq S \Leftrightarrow f_i(l)|w_l(S).
\]
The first polynomials are
$f_1(l)=(2l+1),
f_2(l)=(2l+1)(2l+2),
f_3(l)=(2l+1)(2l+2)(2l+3)(2l+4),
f_4(l)=(2l+1)(2l+2)(2l+3)(2l+4)^2(2l+5)$.
\end{conj}



Our last conjecture is concerning the rational roots weight functions can have.




\begin{conj}
\begin{enumerate}
\item Let $M$ be an irreducible Motzkin path of length $n\geq 8$. The rational roots of $w_l(M)$ lie in $\{-\frac{1}{2},-1,\ldots, -\frac{2n-3}{2},-n+1\}$.
\item Let $S$ be an irreducible centred Catalan set of size $n\geq 11$. The rational roots of $w_l(S)$ lie in 
$\{-\frac{1}{2},-1,\ldots, -\frac{2n-5}{2},-n+2,-\frac{n^2-5n+7}{2(n-3)}\}$.
Further $w_l(S)$ is divisible by $(2(n-3) l+n^2-5n+7)$ if and only if  $S=\{-n+2,-1,0,1 \ldots, n-3\}$ or $S=\{-n+3,\ldots, -1,0,1, n-2\}$.
\end{enumerate}
\end{conj}

\acknowledgements{The author wants to thank Arvind Ayyer for giving him access to his conjectures which has been a major influence for this work.}

\printbibliography

\end{document}
